//MyArrayList只是保存String类型的元素的数据
public class MyArrayList {
    //通过一个数组，来表示顺序表中的元素
    private String[] data = null;
    //当前顺序表中的元素个数
    private int size = 0;

    //构造函数，初始化一个空的顺序表
    public MyArrayList() {
        data = new String[10];
    }

    public MyArrayList(int capacity) {
        if(capacity < 10){
            capacity = 10;
        }
        data = new String[capacity];
    }

    //实现扩容
    private void resize(){
        //1.创建一个新的数组，容量为原数组的1.5倍
        String[] newData = new String[data.length+(data.length>>1)];
        //2.将原数组中的元素复制到新数组中
        for(int i=0;i<size;i++){
            newData[i] = data[i];
        }
        //3.将新数组设置为当前数组
        data = newData;
    }

    //实现尾插
    //时间复杂度O(1)
    public void add(String elem){
        //1.判断当前数组是否已满
        if(size == data.length){
            //2.扩容
            resize();
        }
        //3.将元素添加到数组尾部
        data[size++] = elem;
    }

    //实现头插
    //时间复杂度O(n)
    public void addFirst(String elem){
        //1.判断当前数组是否已满
        if(size == data.length){
            //2.扩容
            resize();
        }
        //3.将元素添加到数组头部
        for(int i=size-1;i>=0;i--){
            data[i+1] = data[i];
        }
        data[0] = elem;
        size++;
    }

    //实现中间位置插入
    //时间复杂度O(n)
    public void add(int index, String elem){
        //1.判断index是否合法
        if(index < 0 || index > size){
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        }
        //2.判断当前数组是否已满
        if(size == data.length){
            //扩容
            resize();
        }
        //3.将元素添加到数组中间位置
        for(int i=size-1;i>=index;i--){
            data[i+1] = data[i];
        }
        data[index] = elem;
        size++;
    }

    //实现删除
    //返回被删除的元素的值
    //时间复杂度O(n)
    public String remove(int index){
        //1.判断index是否合法
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        }
        //2.获取被删除的元素的值
        String elem = data[index];
        //3.将后续元素前移
        for(int i=index+1;i<size;i++){
            data[i-1] = data[i];
        }
        size--;
        return elem;
    }

    //按照元素值来删除元素
    //删除成功，返回true，否则返回false
    //时间复杂度O(n)
    public boolean remove(String elem){
        //1.遍历数组，找到元素
        for(int i=0;i<size;i++){
            if(data[i].equals(elem)){
                //2.删除元素
                remove(i);
                return true;
            }
        }
        //3.未找到元素
        return false;
    }

    //获取指定位置的元素
    //时间复杂度O(1)
    public String get(int index){
        //1.判断index是否合法
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        }
        //2.获取元素
        return data[index];
    }

    //设置指定位置的元素
    //时间复杂度O(1)
    public void set(int index, String elem){
        //1.判断index是否合法
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        }
        //2.设置元素
        data[index] = elem;
    }

    //判断元素是否存在
    //时间复杂度O(n)
    public boolean contains(String elem){
        //1.遍历数组，找到元素
        for(int i=0;i<size;i++){
            if(data[i].equals(elem)){
                //2.返回true
                return true;
            }
        }
        //3.未找到元素
        return false;
    }

    //实现查找
    //返回元素的索引，如果不存在，返回-1
    //时间复杂度O(n)
    public int indexOf(String elem){
        //1.遍历数组，找到元素
        for(int i=0;i<size;i++){
            if(data[i].equals(elem)){
                //2.返回索引
                return i;
            }
        }
        //3.未找到元素
        return -1;
    }

    //实现反向查找
    //返回元素的索引，如果不存在，返回-1
    //时间复杂度O(n)
    public int lastIndexOf(String elem){
        //1.遍历数组，找到元素
        for(int i=size-1;i>=0;i--){
            if(data[i].equals(elem)){
                //2.返回索引
                return i;
            }
        }
        //3.未找到元素
        return -1;
    }

    //实现截取
    //时间复杂度O(n)
    public MyArrayList subList(int fromIndex, int toIndex){
        //1.判断fromIndex和toIndex是否合法
        if(fromIndex < 0 || toIndex > size || fromIndex > toIndex){
            throw new IndexOutOfBoundsException("fromIndex: "+fromIndex+", toIndex: "+toIndex+", Size: "+size);
        }
        //2.创建新的MyArrayList对象
        MyArrayList subList = new MyArrayList(toIndex-fromIndex);
        //3.将子列表中的元素复制到新列表中
        for(int i=fromIndex;i<toIndex;i++){
            subList.add(data[i]);
        }
        //4.返回新列表
        return subList;
    }

    //判断顺序表是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    //获取顺序表的大小
    public int size(){
        return size;
    }

    //清空顺序表
    public void clear(){
        size = 0;
    }

    @Override
    public String toString(){
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for(int i=0;i<size;i++){
            stringBuilder.append(data[i]);
            if(i!= size-1){
                stringBuilder.append(", ");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
}
